package com.zwj.interview.数组.双指针;


/**
 * 输入一个正整数组成的数组和一个正整数k，
 * 请问数组中和大于或等于k的连续子数组的最短长度是多少？如果不存在所有数字之和大于或等于k的子数组，
 * 则返回0。例如，输入数组[5，1，4，3]，k的值为7，和大于或等于7的最短连续子数组是[4，3]，因此输出它的长度2
 */
public class 连续和大于等于目标值的子数组长度 {

    /**
     * 指针P1和P2初始化的时候都指向数组的第1个元素。如果两个指针之间的子数组中所有数字之和大于或等于k，
     * 那么把指针P1向右移动。每向右移动指针P1一步，相当于从子数组的最左边删除一个数字，子数组的长度也减1。
     * 由于数组中的数字都是正整数，从子数组中删除一些数字就能减小子数组之和。由于目标是找出和大于或等于k的最短子数组，
     * 因此一直向右移动指针P1，直到子数组的和小于k为止。如果两个指针之间的子数组中所有数字之和小于k，
     * 那么把指针P2向右移动。指针P2每向右移动一步就相当于在子数组的最右边添加一个新的数字，子数组的长度加1。
     * 由于数组中的所有数字都是正整数，因此在子数组中添加新的数字能得到更大的子数组之和
     */
    public static int minSubArrayLen(int k, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLength = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            //当累计到和大于等于目标值的时候，就尝试移动左边的指针，缩小子数组的长度
            while (left <= right && sum >= k) {
                minLength = Math.min(minLength, right - left + 1);
                //这一步就是缩小数组的长度，右边指针往前推进
                sum -= nums[left++];
            }
        }
        return minLength == Integer.MAX_VALUE ? 0 : minLength;
    }


    public int minLength(int k,int[] nums){
        int left=0;
        int sum=0;
        int minLength=Integer.MAX_VALUE;
        for(int right=0;right<nums.length;right++){
            sum+=nums[right];
            while(left<=right && sum>=k){
                //更新minLength
                minLength=Math.min(minLength,right-left+1);
                sum-=nums[left++];
            }
        }
        return minLength==Integer.MAX_VALUE?0:minLength;
    }



    public static void main(String[] args) {
        System.out.println(minSubArrayLen(7,new int[]{5,1,4,3}));
    }


}
